0926. 将字符串翻转到单调递增【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0。

返回使 s 单调递增的最小翻转次数。

---

示例 1：

输入：s = "00110"
输出：1
解释：翻转最后一位得到 00111.

示例 2：

输入：s = "010110"
输出：2
解释：翻转得到 011111，或者是 000111。

示例 3：

输入：s = "00011000"
输出：2
解释：翻转得到 00000000。

---

提示：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'

2. 🎯 s.1 - 动态规划

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {string} s
 * @return {number}
 */
var minFlipsMonoIncr = function (s) {
  let ones = 0
  let flips = 0

  for (const ch of s) {
    if (ch === '1') {
      ones++
    } else {
      flips = Math.min(flips + 1, ones)
    }
  }

  return flips
}

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(1)$，只使用常数额外空间

算法思路：

• 维护 ones（已遍历的 1 的个数）和 flips（使当前前缀单调递增的最小翻转次数）

• 遇到 '1' 时 ones++；遇到 '0' 时，要么将其翻转为 1（flips + 1），要么将之前所有的 1 翻转为 0（ones），取较小值

• 返回 flips

• 时间复杂度：$O(1)$

• 空间复杂度：$O(1)$